package com.ds.seqlist;

public class SingleLinkedList {
    // 链表的头节点
    private Node head = null;
    // 当前链表中Node节点的个数 = 有效数值的个数
    private int size = 0;

    /**
     * 向当前的链表中添加一个新的节点，默认在链表的头部添加
     * @param val
     */
    public void addFirst(int val) {
        Node newNode = new Node();
        // 保存值
        newNode.val = val;
        if(head != null) {
            newNode.next = head;
        }
        // 无论是否为空，新节点都是插入后的链表头结点
        head = newNode;
        size ++;
    }

    public void add(int index,int val) {
        // 1.若index位置非法的
        if (index < 0 || index > size) {
            System.err.println("add index illegal!");
            return;
        }
        // 2.插入任意位置要找到前驱结点，但是链表中有一个结点没有前驱
        // 头结点没有前驱！！！
        if (index == 0) {
            // 头插！
            addFirst(val);
        }else {
            // 3.当前索引合法且不是在数组的头部插入,就要找到插入位置的前驱结点
            Node newNode = new Node();
            newNode.val = val;
            Node prev = head;
            for (int i = 0; i < index - 1; i++) {
                prev = prev.next;
            }
            // 此时prev一定指向了待插入节点的前驱
            newNode.next = prev.next;
            prev.next = newNode;
            size ++;
        }
    }

    /**
     * 在链表的尾部插入新元素
     * @param val
     */
    public void addLast(int val) {
        add(size,val);
    }

    /**
     * 查找第一个值为val的结点索引是多少
     * @param val
     * @return
     */
    public int getByValue(int val) {
        int index = 0;
        for (Node x = head;x != null;x = x.next) {
            if (x.val == val) {
                // 第一个值为val的节点
                return index;
            }
            index ++;
        }
        // 说明当前链表中根本就没有值为val的结点，返回-1,表示不存在
        return -1;
    }

    public boolean contains(int val) {
        int index = getByValue(val);
        return index != -1;
//        if (index == -1) {
//            return false;
//        }
//        return true;
//        return getByValue(val) != -1;
//        for (Node x = head;x != null;x = x.next) {
//            if (x.val == val) {
//                return true;
//            }
//        }
//        return false;
    }

    /**
     * 查询索引为index位置的结点值
     * @param index
     * @return
     */
    public int get(int index) {
        // 1.判断index的合法性
        // IDEA快速修正快捷键 alt + enter
        if (rangeCheck(index)) {
            Node x = head;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
            return x.val;
        }
        System.err.println("index illegal!get error");
        return -1;
    }

    /**
     * 修改索引为index位置的结点值为newVal，返回修改前的节点值
     * @param index
     * @param newVal
     * @return
     */
    public int set(int index,int newVal) {
        if (rangeCheck(index)) {
            Node x = head;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
            int oldVal = x.val;
            x.val = newVal;
            return oldVal;
        }
        System.err.println("index illegal!set error");
        return -1;
    }

    /**
     * 删除单链表中索引为index位置的节点，返回删除前的节点值
     * @param index
     * @return
     */
    public int remove(int index) {
        if (rangeCheck(index)) {
            if (index == 0) {
                // 删除头结点
                Node x = head;
                head = head.next;
                size --;
                x.next = null;
                return x.val;
            }else {
                // 此时删除的是链表的中间结点
                // 找前驱！
                Node prev = head;
                for (int i = 0; i < index - 1; i++) {
                    prev = prev.next;
                }
                // prev就是待删除节点的前驱
                // node节点就是待删除的结点
                Node node = prev.next;
                prev.next = node.next;
                node.next = null;
                size --;
                return node.val;
            }

        }
        System.err.println("remove index illegal!");
        return -1;
    }

    /**
     * 删除链表中第一个值为val的元素
     * @param val
     */
    public void removeValueOnce(int val) {
        if (head == null) {
            System.err.println("链表为空，无法删除");
            return;
        }
        if (head.val == val) {
            // 此时头结点就是第一个值为val的结点
            Node x = head;
            head = head.next;
            x.next = null;
            size --;
        }else {
            // 当前头结点不是待删除的结点，需要遍历
            // 这里同样找到待删除的前驱结点
            // 能否知道前驱结点移动步数？
            Node prev = head;
            while (prev.next != null) {
                // 至少还有后继结点
                if (prev.next.val == val) {
                    // 此时prev.next就是待删除的结点
                    Node node = prev.next;
                    prev.next = node.next;
                    node.next = null;
                    size --;
                    return;
                }
                prev = prev.next;
            }
        }
    }

    /**
     * 删除链表中所有值为val的结点
     * @param val
     */
    public void removeAllValue(int val) {
        while (head != null && head.val == val) {
            // 头节点就是待删除节点
            Node x = head;
            head = head.next;
            x.next = null;
            size --;
        }
        // 头节点一定不是待删除的节点
        // 判空
        if (head == null) {
            // 链表删完了
            return;
        }else {
            Node prev = head;
            while (prev.next != null) {
                // 至少还有后继结点
                if (prev.next.val == val) {
                    // 此时prev.next就是待删除的结点
                    Node node = prev.next;
                    prev.next = node.next;
                    node.next = null;
                    size --;
                }else {
                    // 只有当prev.next.val != val才能移动prev指针！
                    prev = prev.next;
                }
            }
        }
    }

    public int removeFirst() {
        return remove(0);
    }

    public int removeLast() {
        return remove(size - 1);
    }


    private boolean rangeCheck(int index) {
        // size是当前有效元素的下一个索引
        if (index < 0 || index >= size) {
            return false;
        }
        return true;
    }


    public String toString() {
        String ret = "";
//        Node x = head;
//        while (x != null) {
//            ret += x.val;
//            ret += "->";
//            x = x.next;
//        }
        for (Node x = head;x != null;x = x.next) {
            ret += x.val;
            ret += "->";
        }
        ret += "NULL";
        return ret;
    }
}

/**
 * 单链表的具体的每个节点 - 车厢类
 */
class Node {
    int val; // 每个节点保存的值
    Node next; // 当前节点的下一个节点地址。

    public Node() {}

    public Node(int val) {
        this.val = val;
    }
    public Node(int val, Node next) {
        this.val = val;
        this.next = next;
    }
}

